0%

【算法学习】AcWing 899. 编辑距离(dp)

发表于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

AcWing 902. 最短编辑距离

题目描述

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。

输入格式

1
2
3
4
5
第一行包含整数n，表示字符串A的长度。
第二行包含一个长度为n的字符串A。
第三行包含整数m，表示字符串B的长度。
第四行包含一个长度为m的字符串B。
字符串中均只包含大写字母。

输出格式

1
输出一个整数，表示最少操作次数。

数据范围

1
1≤n,m≤1000

输入样例：

1
2
3
4
10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

1
4

解题思路

二维dp问题

  • 状态表示:
    • dp[i][j]表示第一个字符串的前i个字母编辑到第二个字符串的前j个字母的最小编辑距离
  • 状态计算:
    • 枚举字符串a前i个字母到字符串b前j个字母的最后一步的操作(增/删/改)
    • 添加一个字母:
      • 要先做到a的前i个字母与b的前j - 1个字母匹配, a[1~i]添加一个字母才能与b[1~j]匹配
      • dp[i][j] = dp[i - 1][j] + 1
    • 删除一个字母:
      • 要先做到a的前i - 1个字母与b的前j个字母匹配，a[1~i]添加一个字母才能与b[1~j]匹配
      • dp[i][j] = dp[i][j - 1] + 1
    • 修改一个字母
      • 要先做到a[1~i-1]与b[1~j-1]匹配
      • a[i]与b[j]相同: dp[i][j] = dp[i - 1][j - 1]
      • a[i]与b[j]不同: dp[i][j] = dp[i - 1][j - 1] + 1
    • 状态转移方程：
      • dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (a[i] != b[j]))

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
// f[i][j]表示A[1~i]到B[1~j]最小的编辑距离
int f[N][N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        f[i][0] = i;
    }
    cin >> m;
    for(int i = 1; i <= m; i ++)
    {
        cin >> b[i];
        f[0][i] = i;
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j++)
        {
            // 枚举最后一步的编辑方式(添加/删除/修改), 取最小值
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + int(a[i] != b[j]));
        }
    cout << f[n][m] << endl;
    return 0;
}

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
    n = int(input())
    a = ' '+ input()
    m = int(input())
    b = ' ' + input()
    
    # 初始化
    f = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        f[i][0] = i
    for i in range(1, m + 1):
        f[0][i] = i
        
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 取三种操作的最小值
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + (a[i] != b[j]))
            
    print(f[n][m])
    
main()

AcWing 899. 编辑距离

给定n个长度不超过10的字符串以及m次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数n和m。

接下来n行，每行包含一个字符串，表示给定的字符串。

再接下来m行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过10。

输出格式

输出共m行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

1
1≤n,m≤1000,

输入样例：

1
2
3
4
5
6
3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
2
1
3

解题思路

最短编辑距离的应用, 求n次最短编辑距离

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

const int N = 1010, M = 20;

int n, m;
char s[N][M];
int f[M][M];

// a是否能在<=t的次数下编辑到b

bool can_solve(char a[], char b[], int t) {
    int la = strlen(a + 1), lb = strlen(b + 1);

    // 初始化
    f[0][0] = 0;
    for (int i = 1; i <= la; i++) f[i][0] = i;
    for (int i = 1; i <= lb; i++) f[0][i] = i;

    //求a最小需要编辑多少次可以到b
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + int(a[i] != b[j]));
        }

    return f[la][lb] <= t;
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i] + 1;
    while(m --) {
        int res = 0;
        int t;
        char q[M];
        
        cin >> q + 1 >> t;
        for (int j = 0; j < n; j++) res += can_solve(s[j], q, t);
        cout << res << endl;
    }
    return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def can_solve(a, b, t):
    """
    求字符串a是否能在t的次数内编辑到b
    为了方便计算, a和b在前面随便加个字符占位
    """
    a = ' ' + a
    b = ' ' + b
    la, lb = len(a), len(b)
    dp = [[0] * lb for _ in range(la)]

    # 初始化：a[i]到空字符串的编辑距离为i, 空字符串到b[i]的编辑距离也是i
    for i in range(la):
        dp[i][0] = i
    for i in range(lb):
        dp[0][i] = i

    for i in range(1, la):
        for j in range(1, lb):
            # dp[i][j]: a的前i个字母到b的前j个字母的最短编辑距离
            # 枚举最后一步的编辑方式: 增 dp[i - 1][j] + 1, 删 dp[i][j - 1] + 1, 改dp[i - 1][j - 1] + 1
            # 如果a[i] == b[j] 不需要编辑, 直接是dp[i - 1][j - 1]
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (a[i] != b[j]))

    return dp[la - 1][lb - 1] <= t

def main():
    n, m = [int(x) for x in input().split()]
    s = []
    for _ in range(n):
        s.append(input())
    for _ in range(m):
        q, t = input().split()
        t = int(t)
        res = 0
        for i in range(n):
            res += can_solve(s[i], q, t)
        print(res)

main()